package practice1_100;

public class Practice1269 {
    public int numWays(int steps, int arrLen) {
        int mod = (int)1e9+7;
        int current =0;
        int dpTable[][] =new int [steps+1][arrLen];
        dpTable[steps][0]=1;
        for(int j=0;j<arrLen;j++){
            for(int i=steps-1;i>=0;i--){
                if(j==0) dpTable[i][j]=dpTable[i+1][j]+dpTable[i+1][j+1];
                else if(j==arrLen-1) dpTable[i][j]=dpTable[i+1][j]+dpTable[i+1][j-1];
                else dpTable[i][j]=dpTable[i+1][j]+dpTable[i+1][j-1]+ dpTable[i+1][j+1];
            }
        }
        return dpTable[0][0];
    }

    public static void main(String[] args) {
        int res=new Practice1269().numWays(3,2);
        System.out.println(res);
    }
}
